#include <iostream>
#include <stdlib.h>
#include <list>
#include <vector>
#include <stdio.h>
#include <string.h>
#include "grafo.h"
#include <algorithm>

void execGrasp(vector<int> title, vector< vector<int> > v){
  int nodesCant = title[0];
  int edgesCount = title[1];
  int origen = title[2];
  int destino = title[3];
  int K  = title[4];
  timeval tm1, tm2;
  gettimeofday(&tm1, NULL);
  origen --;
  destino --;
  if (destino<origen) swap(destino,origen);

  Graph *G = new Graph;
  initGraph(G,nodesCant);
  busquedaGrasp(G,nodesCant,v,origen,destino,K);

  gettimeofday(&tm2, NULL);
  unsigned long long t = 1000 * (tm2.tv_sec - tm1.tv_sec) + (tm2.tv_usec - tm1.tv_usec) / 1000;
  printf("%ld %lld %s",nodesCant,t, "\n");
}


int main(int argc, char** argv) {

  srand (time(NULL));
  char line[1000];
  vector<int> reader;
  reader.resize(5);
   char* strVal;
   int val;
         int readedLine = 0;

  vector <int> instanceTitle (5);
  vector< vector<int> > values;

   while ( cin.getline(line,50,'\n') && line != "0" ){
    if ((readedLine == 0 &&  0 < instanceTitle.at(4)) ){
      // execCacm(instanceTitle,values);
      execGrasp(instanceTitle,values);
      if (line[0] == '0'){
        return 0;
      }

    }
    if(readedLine == 0){

      strVal = strtok(line," ");
      for (int i =0 ; i< 5; i++){
        val = atoi(strVal);
        instanceTitle[i] = atoi(strVal);
        strVal = strtok(NULL," ");
      }
      readedLine = instanceTitle[1];
      values.resize(instanceTitle[1]);
    }else{

      values[(instanceTitle[1] - readedLine)].resize(4);

      strVal = strtok(line," ");
      for (int i =0 ; i< 4; i++){
        val = atoi(strVal);
        values[(instanceTitle[1] - readedLine)][i] = atoi(strVal);
        strVal = strtok(NULL," ");
      }
      readedLine --;
    }
  }

    return 0;
}
